A
弱智题,交叉相乘判一下倍数关系即可。
Code
#include <cstdio>
long long T, a, b, c, d;
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
a *= d, b *= c;
if (a == b) puts("0");
else if (a == 0 || b == 0) puts("1");
else if (a < b) {
if (b % a == 0) puts("1");
else puts("2");
} else {
if (a % b == 0) puts("1");
else puts("2");
}
}
}
B
记录整个数组的最大值 ,次大值 ,最小值 ,次小值 。容易找到一种划分 使得答案为 。显然这是最优的答案。
Code
#include <cstdio>
const int N = 1e5 + 5;
int T, mx1, mx2, mn1, mn2, n, a;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
mx1 = mx2 = 0;
mn1 = mn2 = 2e9;
for (int i = 1; i <= n; i++) {
scanf("%d", &a);
if (a > mx1) mx2 = mx1, mx1 = a;
else if (a > mx2) mx2 = a;
if (a < mn1) mn2 = mn1, mn1 = a;
else if (a < mn2) mn2 = a;
}
printf("%lld\n", 1LL * (mx1 + mx2 - mn1 - mn2));
}
}
C
注意到在一个满足要求的L形里面,有 个格子是 是最优的消除方式 ,而消除过后又会产生一个新的L形满足要求。
于是我们便可以找到一个有 个 的L形,从这里开始不断消除,如果找不到只能浪费一些 。
整个方格表扫一遍即可,时间复杂度 。
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 505;
int a[N][N], n, m, sum, mn, T;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
sum = 0;
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%1d", &a[i][j]);
sum += a[i][j];
}
mn = 0x7fffffff;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++) {
int cnt = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
if (cnt) mn = min(mn, max(1, cnt - 1));
}
if (sum == 0) puts("0");
else printf("%d\n", 1 + sum - mn);
}
}
D1
考虑dp。设 为以 结尾的最长的合法子序列长度,则有
朴素转移时间复杂度 ,过不去,怎么办?
考虑缩小 的枚举范围。注意到当 时,在不考虑二进制下最后 位的情况下同样有 。
由于 ,所以在 中 只会对最后 位造成影响,所以 不会成立,故只需从 枚举即可。
时间复杂度降至 ,可以通过 D1 。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5 + 5;
inline int read() {
register int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -f;
ch = getchar();
}
while ('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f == -1 ? -x : x;
}
int a[N], dp[N], n, ans, T;
int main() {
T = read();
while (T--) {
n = read();
for (int i = 0; i < n; i++) a[i] = read();
ans = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = max(i - 255, 0); j < i; j++) {
if ((a[j] ^ i) < (a[i] ^ j))
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
}
}
D2
待补。
E
待补。